package com.github.yangyishe.p300;

import java.util.Arrays;

/**
 * 283. 移动零
 * https://leetcode.cn/problems/move-zeroes/description/?envType=study-plan-v2&envId=top-100-liked
 *
 * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
 *
 * 请注意 ，必须在不复制数组的情况下原地对数组进行操作。
 *
 *
 *
 * 示例 1:
 *
 * 输入: nums = [0,1,0,3,12]
 * 输出: [1,3,12,0,0]
 * 示例 2:
 *
 * 输入: nums = [0]
 * 输出: [0]
 *
 *
 * 提示:
 *
 * 1 <= nums.length <= 104
 * -231 <= nums[i] <= 231 - 1
 *
 *
 * 进阶：你能尽量减少完成的操作次数吗？
 */
public class Problem283 {
    public static void main(String[] args) {
        int[] nums=new int[]{0,1,0,3,12};

        Problem283 problem283 = new Problem283();
        problem283.moveZeroes(nums);
        System.out.println("Arrays.toString(nums) = " + Arrays.toString(nums));

    }

    /**
     * 思路:
     * 快慢指针.
     * 快指针遍历, 慢指针记录0出现的第一个位置.
     * 第一次指向0时, 满指针初始化
     * 每次快指针指向非0值且慢指针已经初始化, swap 快慢指针所指元素, 同时慢指针+1.
     * @param nums
     */
    public void moveZeroes(int[] nums) {
        int slow=-1;

        for(int i=0;i<nums.length;i++){
            if(nums[i]==0){
                if(slow==-1){
                    slow=i;
                }
            }else{
                if(slow!=-1){
                    int temp=nums[slow];
                    nums[slow]=nums[i];
                    nums[i]=temp;

                    slow++;
                }
            }
        }
    }
}
